Random numbers, occurring in digital form as random bit sequences, are often required in applications relevant to security. For example random numbers have to be generated and used in connection with asymmetric authenticating methods. Especially in the case of RFID tags having a security functionality it is necessary to generate corresponding random numbers with particularly few hardware resources. What is desirable therein is to employ only digital logic circuits that can be favorably implemented in terms of cost and effort.
Random-number generators were employed in the past with use being made of, for example, analog noise sources whose signals were digitized. However, hybrid analog/digital circuits are always costly to implement.
In order to generate real random bit sequences a physical random source that is generally difficult to use in computer systems is, as a rule, necessary. In the case of hardware random-number generators a physical process is used as the random source. Sensors then have to be used, though, to register and take measurements from the physical system, with the random data able then to be extracted from the measured data. What can be cited as instances of randomly determined physical processes are radioactive decay, noise in semiconductors, free-running oscillators, and quantum statuses of photons. Although good randomizing of random data can be achieved thereby, the requisite measuring equipment is exceptionally costly so that an application in mass articles, for example for simple encrypting of data on RFID tags, is uneconomical. Moreover, a frequent problem in the case of purely electrically operated random-number generators is that the correct operating mode depends on the need for analog electronic circuits to be set precisely to predefined work points. Thus problems will arise in the event of manufacturing dispersions and changes to the operating conditions such as temperature and other external influences. It is therefore disadvantageous because purely analog circuits are sensitive to interference and manipulation.
What are termed pseudo-random numbers can be generated algorithmically. Although not actually random, the algorithmically generated random bits or random numbers ought therein to be as far as possible indistinguishable from real random bits. In the case of pseudo-random bits a microprocessor device CPU (=Central Processing Unit) is operated by means of a corresponding program that requires what is termed a seed value from a memory. From the seed's current value the CPU computes random bits and new values of the seed, which are in turn stored and overwrite the old value. In order not to obtain the same random-bit or number sequences on different devices, the various devices are in a personalizing step set to an individual start value.
Although they do indeed supply sufficiently random data for many applications, pseudo-random numbers cannot completely replace physical random numbers. That is because genuine randomness is needed at least for determining an initial seed value. The pseudo-random numbers are, though, deterministic proceeding from the initial seed value. The statistical quality of generated pseudo-random data is therein highly dependent on the algorithm employed and the length of the seed value. For example methods employing Fibonacci generators are used in C standard libraries. Feedback shift registers are also sometimes used for generating pseudo-random numbers. The aforementioned measures are unsuitable for cryptographic applications. An attacker could too easily predict the random number sequence.
More complex methods employ cryptographically powerful hash functions or encryption techniques to compute random data and new seed values from a current seed value. CPUs requiring particularly efficient resources are therefore necessary for achieving adequate quality in generating random numbers.
In the past it was also proposed that purely digital random-number generators having digital electric components in integrated circuits be provided. For example it was proposed using the jitter in ring oscillators for random-number generation. Digital ring oscillators are embodied usually from an odd number of inverters that are arranged cyclically or, as the case may be, provide mutual feedback. The fluctuations in the period lengths are therein referred to as jitter. The jitter is, though, as a rule small compared with the period length so that its randomness accumulates only slowly over time. To generate random numbers more quickly, Fibonacci or Gallois ring-oscillator variants have been proposed by means of which random-number sequences can be generated faster.
While it is true that the digitally implemented random-number generators can be favorably produced, for example as FPGAs or in ASICs (Application-Specific Integrated Circuits), production variations in the relevant components disrupt the process of random-number generation. Algorithmic post-processing is also employed to compensate statistical defects in the random data due to, for instance, physical noise sources. The measurement data is therein compressed to achieve an increase in entropy. Cryptographically powerful hash functions can also be used to balance out fluctuations in frequency distribution.
Overall, the known methods and generators for random-bit generation or, as the case may be, the corresponding hardware implementations are associated with a number of disadvantages that as a rule preclude their use in mass products.